from typing import List
"""
 使用一维数组做dp
 想在一次循环中实现,感觉有点难
"""
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        if m == 0:
            return 0
        n = len(obstacleGrid[0])
        dp = [0] * len(obstacleGrid) # 由于第一行可能也有障碍,所以只能初始化0

        
        skip = False
        for i in range(n):
            if obstacleGrid[0][i] == 1:
                print("xx1")
                dp[0] = 0
                skip = True
            for j in range(m):
                
                if obstacleGrid[j][i] == 1:
                    if j == 0 or i==0:
                        dp[j] = 0
                        continue
                    else:
                        dp[j] = 0
                else:
                    if not skip and (j ==0 or i==0):
                        print("xx")
                        dp[j] = 1
                    else:
                        dp[j] = dp[j] + dp[j-1]
            print(dp)
        return dp[-1]
# 
# s = [
#   [0,0,0],
#   [0,1,0],
#   [0,0,0]
# ]
s = [[1, 0]]
Solution().uniquePathsWithObstacles(s)

def test():
    s = [[0, 1]]
    assert Solution().uniquePathsWithObstacles(s) == 0

def test1():
    s = [[1, 0]]
    assert Solution().uniquePathsWithObstacles(s) == 0

def test2():
    s = [[0, 1, 0]]
    assert Solution().uniquePathsWithObstacles(s) == 0